class Solution(object):
    def sumCounts(self, nums):
        base = 10 ** 9 + 7
        n = len(nums)
        st = [0] * 4 * n
        rank = [0] * 4 * n
        d = {}
        last = [-1] * n
        for i in range(n - 1, - 1, -1):
            num = nums[i]
            if num in d:
                last[d[num]] = i
                d[num] = i
            else:
                d[num] = i
        ls = 0
        rs = n - 1
        def update(node, ls, rs, l, r, val):
            if l <= ls and r >= rs:
                rank[node] += val
                st[node] += val * (rs - ls + 1)
                return st[node]             
            else:
                mid = (ls + rs) // 2
                down_load(node, ls, rs)
                left_val = 0
                right_val = 0
                if l <= mid:
                    left_val = update(2 * node + 1, ls, mid, l, r, val)
                if r >= mid + 1:
                    right_val = update(2 * node + 2, mid + 1, rs, l, r, val)
                st[node] = st[2 * node + 1] + st[2 * node + 2]
                return left_val + right_val

        def down_load(node, ls, rs):
            mid = (ls + rs) // 2
            rank[2 * node + 1] += rank[node]
            st[2 * node + 1] += rank[node] * (mid - ls + 1)
            rank[2 * node + 2] += rank[node]
            st[2 * node + 2] += rank[node] * (rs - mid)
            rank[node] = 0

        ans = 0
        last_num = 0
        for index, num in enumerate(nums): 
            last_total = update(0, ls, rs, last[index] + 1, index, 1)
            now_num = (2 * last_total + last_num - (index - last[index])) % base
            last_num = now_num
            ans = (ans + now_num) % base
        return ans




data = Solution()
nums = [1,2,1]
print(data.sumCounts(nums))
nums = [2,2]
print(data.sumCounts(nums))